import heapq
import collections


class DSU:
    def __init__(self):
        self.parent = {}

    def find(self, node):
        if node not in self.parent or self.parent[node] == node:
            return node
        else:
            node_parent = self.find(self.parent[node])
            self.parent[node] = node_parent
            return node_parent

    def union(self, node1, node2):
        parent1 = self.find(node1)
        parent2 = self.find(node2)
        self.parent[parent2] = parent1


class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: list) -> str:
        dsu = DSU()
        for pair in pairs:
            dsu.union(pair[0], pair[1])
        switch = collections.defaultdict(list)
        for i in range(len(s)):
            heapq.heappush(switch[dsu.find(i)], s[i])

        res = list(s)
        for i in range(len(s)):
            res[i] = heapq.heappop(switch[dsu.find(i)])

        return "".join(res)
